﻿using System.Text;

namespace Graph;

public class DiAdjDictionary : IDiGraph
{
    private Dictionary<int, float>[] graph;//记录每个顶点到所有邻接点（键）的边权值（值）

    public int V { get; }
    public int E { get; }

    public DiAdjDictionary(string file)
    {
        StreamReader sr = new StreamReader(file);

        string line = sr.ReadLine();
        string[] str = line.Split(' ');

        V = int.Parse(str[0]);
        E = int.Parse(str[1]);

        //空间复杂度 O（V*V）
        graph = new Dictionary<int, float>[V];
        for (int i = 0; i < V; i++)
        {
            graph[i] = new Dictionary<int, float>();
        }

        //建图时间复杂度 O（E）
        for (int i = 0; i < E; i++)
        {
            line = sr.ReadLine();
            str = line.Split(' ');

            int a = int.Parse(str[0]);
            int b = int.Parse(str[1]);
            int w = int.Parse(str[2]);

            //有向图
            graph[a].Add(b, w);
            //graph[b].Add(a, w);
        }

        sr.Close();
    }

    //查看两点是否相邻 O（1）
    public bool HasEdge(int a, int b)
    {      
        return graph[a].ContainsKey(b);
    }

    //求一个点的相邻顶点集 O（V）
    public IEnumerable<int> Adj(int a)
    {
        return graph[a].Keys;
    }

    //顶点a的相邻点数 O（1）
    public int Degree(int a)
    {
        return Adj(a).Count();
    }

    public int InDegree(int a)
    {
        return InAdj(a).Count();
    }

    public int Degrees(int a)
    {
        return Degree(a) + InDegree(a);
    }

    public IEnumerable<int> InAdj(int a)
    {
        List<int> res = new List<int>();

        for (int b = 0; b < V; b++)
        {
            if (HasEdge(b, a))
            {
                res.Add(b);
            }
        }

        return res;
    }

    //(a,b)边权值 O（1）
    public float GetWeight(int a, int b)
    {
        if (HasEdge(a, b))
        {
            return graph[a][b]; //第一维：顶点a为索引的字典数组元素，第二维：顶点b为键的字典值
        }

        return float.PositiveInfinity;
    }

    //打印图信息，输出邻接表
    public override string ToString()
    {
        StringBuilder sb = new StringBuilder();
        sb.Append(string.Format("V = {0}, E={1}\n", V, E));
        for (int a = 0; a < V; a++)
        {
            sb.Append(a + " : ");
            foreach (var kvp in graph[a])
            {
                sb.Append($"(V = {kvp.Key}, W={kvp.Key}) ");
            }
            sb.Append("\n");
        }
        return sb.ToString();
    }

    //验证
    static void Main(string[] args)
    {
        IGraph graph = new AdjDictionary("带权图/g.txt");
        Console.WriteLine(graph);

        Console.WriteLine(graph.HasEdge(0, 1));

        var adjs = graph.Adj(0);
        foreach (var v in adjs)
        {
            Console.Write(v + " ");
        }
        Console.WriteLine();

        Console.WriteLine(graph.Degree(0));

        Console.Read();
    }
}
